import java.util.Arrays;

public class 字符串编辑距离 {

    public static void main(String[] args) {
        System.out.println(getStrDistance("件号类型","零件号类型"));

    }

    public static int getStrDistance(String a, String b) {
        if (a == null || b == null) {
            return 1000;
        }

        // 初始化用于记录状态转移的二维表，因为状态转移是从空字符串开始，所以需要比原字符的长度加一
        int[][] d = new int[a.length() + 1][b.length() + 1];

        // 如果i为0，且j大于等于0，那么d[i, j]为j
        for (int j = 0; j <= b.length(); j++) {
            d[0][j] = j;
        }

        // 如果i大于等于0，且j为0，那么d[i, j]为i
        for (int i = 0; i <= a.length(); i++) {
            d[i][0] = i;
        }

        // 实现状态转移方程，d[i, j]=min(d[i-1, j] + 1, d[i, j-1] + 1, d[i-1, j-1] + r(i, j))
        // 垂直上方单元格的值和水平前方单元格的值总是加一，替换函数由左上方单元格的值加一或加零
        // 因为下标从0开始，代码里的状态转移是从d[i, j]到d[i+1, j+1]，而不是从d[i-1, j-1]到d[i, j]。本质上是一样的。
        for (int i = 0; i < a.length(); i++) {
            for (int j = 0; j < b.length(); j++) {

                int r = 0;
                if (a.charAt(i) != b.charAt(j)) {
                    r = 1;
                }

                int first_append = d[i][j + 1] + 1;
                int second_append = d[i + 1][j] + 1;
                int replace = d[i][j] + r;

                int min = Math.min(first_append, second_append);
                min = Math.min(min, replace);
                d[i + 1][j + 1] = min;

            }
        }
        for (int[] arr : d) {
            System.out.println(Arrays.toString(arr));
        }
        return d[a.length()][b.length()];
    }
}
